package leetcode_200;

import java.util.ArrayList;
import java.util.List;

import helpclass.TreeNode;

/**
 *@author 周杨
 *BinarySearchTreeIterator_173 创建二叉搜索树的遍历器
 *describe:用栈 AC 30%
 *2018年6月9日 下午3:16:28
 */
public class BinarySearchTreeIterator_173 {
    List<TreeNode> list;
	public static void main(String[] args) {
		TreeNode root=new TreeNode(2);
		root.left=new TreeNode(1);
		root.right=new TreeNode(3);
		BinarySearchTreeIterator_173 test=new BinarySearchTreeIterator_173(root);
		while(test.hasNext()) {
			System.out.println(test.next());
		}

	}
	
	public BinarySearchTreeIterator_173(TreeNode root) {
		list =new ArrayList<TreeNode>();
		while(root!=null) {
			list.add(root);
			root=root.left;
		}
		
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(list.size()>0)
        	return true;
        return false;
    }

    /** @return the next smallest number */
    public int next() {
    	TreeNode node=this.list.get(list.size()-1);
    	int res=node.val;
    	this.list.remove(node);
    	node=node.right;
    	while(node!=null) {
    		this.list.add(node);
    		node=node.left;
    	}
    	return res;
    }

}
